package com.structure.algorithm;

/**
 * 二叉搜索树的后序遍历
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
 * 如果是返回true，否则返回false。假如输入的数组的任意两个数字都互不相同。
 * Created by sucre on 2015/11/1.
 */
public class BehindSquenceOfBST {
    private boolean verifySquenceOfBST(int[] squence,int length){
        if(squence ==null || length <=0){
            return false;
        }
        int root = squence[length -1];
        //在二叉搜索树中左子树的结点小于根结点
        int i =0;
        for(;i<length -1;++i){
            if(squence[i] > root){
                break;
            }
        }
        //在二叉树中右子树的结点大于根结点
        int j =i;
        for(;j<length -1;++j){
            if(squence[j] < root){
                break;
            }
        }
        //判断左子树是否二叉搜索树
        boolean left = true;
        if(i>0){
            left = verifySquenceOfBST(squence,i);
        }
        //判断右子树是否是二叉搜索结
        boolean right = true;
        if(i < length -1){
            right = verifySquenceOfBST(squence,length -i -1);
        }
        return (right & left);
    }
}
